package SortAlgorithm;

/**
 * @author zxc
 * @date 2023/01/15 21:08
 **/

import LinkedList.ListNode;

/**
 *  题目 ：合并排序链表
 *  题目详述 ：
 *  给定一个链表数组，每个链表都已经按升序排列。
 *  请将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class MergeKLists_MergeSorted {
    /**
     * 思路 ：归并排序
     * 核心，在于归并排序中merge方法（merge方法，作用为 对于两条排序链表进行合并操作，将其合并为一条排序后的链表）
     * （1）将链表数组划分为一条条排序链表（记住，划分的细粒度 ：一条链表的程度）；同时，两两进行子链表合并merge操作；
     * （2）对于划分的排序链表，逐步地进行合并操作，直至完成最终合并；
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 若是存储排序链表的数组为空的话，则直接返回null即可
        /**
         * 问题 ：为什么 lists == null不能够去判断当前lists链表数组为空呢？
         * 原因 ：在于 lists为链表数组，
         * （1）若是链表的话，则可以通过 list == null，来判断其是否为null；
         * （2）若是数组的话，数组为空则需要通过数组长度是否为0 来进行判断；
         */
        if(lists.length == 0){
            return null;
        }
        return mergeList(lists , 0 , lists.length);
    }
    // mergeList函数 ：对于链表数组lists，将其划分为单条排序链表;
    private ListNode mergeList(ListNode[] lists, int start, int end) {
        // 即，链表数组被划分为单个链表数组
        if(start + 1 == end){
            return lists[start];
        }
        // 对于链表数组lists进行归并排序；
        // 只不过，链表数组中每个数组元素所存储的是链表;
        // 即，对于每个数组元素（即，排序链表）进行合并
        int mid = (start + end) / 2;
        // 需要注意的是，归并排序的核心在于 如何划分要去进行合并的子数组/子链表；
        /**
         * 递归实现 ：即，通过mid = （start + end） / 2 快速对于 所要划分成子数组/子链表的数组/链表 进行划分；
         * 迭代实现 ：即，两层for循环
         * （1）外层for循环，即是所要进行合并操作的次数；（一般为logk，k为所需要进行排序的数组/链表中元素总数）
         * （2）内层for循环，即是将长度为step的子数组/子链表 合并为 长度为2step的数组/链表；
         */
        ListNode head1 = mergeList(lists , start , mid);
        ListNode head2 = mergeList(lists , mid , end);
        return merge(head1 , head2);
    }
    // merge函数 ：对于两台排序好的子链表，将其合并为一条排序好的链表;
    private ListNode merge(ListNode head1, ListNode head2) {
        // 将长度为step的两个子链表 merge合并为长度为2step的链表
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                node.next = head1;
                head1 = head1.next;
            }
            else {
                node.next = head2;
                head2= head2.next;
            }
            node = node.next;
        }
        node.next = head1 != null ? head1 : head2;
        // 返回新构建链表的头结点
        return dummy.next;
    }
    /**
     * 分析 ：
     * （1）空间复杂度 ：由于递归调用栈 深度为logn（n，为链表数组中的链表总数）
     * （2）时间复杂度 ：O（nlogk）
     *  由于所需要去进行合并的节点数为n，同时对于链表数组进行递归划分为子数组（即，指的是每个链表数组元素所对应排序链表）所需要划分的时间复杂度 ：O（logk）（k，为链表数组中的链表总数）
     *  ===》 综上所述，总的时间复杂度为 ：O（nlogk）
     */
}
